/* 
 * File:   TestSelectionSort.cpp
 * Author: marco
 * 
 * Created on December 7, 2009, 11:38 AM
 */

#include <alg/SelectionSort.h>
#include <alg/InPlaceComparer.h>
#include <gtest/gtest.h>

TEST(SelectionSortTest, TestOneElement) {
    std::vector<std::size_t> v;
    v.push_back(1);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::SelectionSort<std::vector<std::size_t> > selectionSort(v, comparer);
    selectionSort.sort();
    EXPECT_EQ(1, v[0]);
}

TEST(SelectionSortTest, TestTwoElementsSorted) {
    std::vector<std::size_t> v;
    v.push_back(1);
    v.push_back(2);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::SelectionSort<std::vector<std::size_t> > selectionSort(v, comparer);
    selectionSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
}

TEST(SelectionSortTest, TestTwoElementsUnsorted) {
    std::vector<std::size_t> v;
    v.push_back(2);
    v.push_back(1);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::SelectionSort<std::vector<std::size_t> > selectionSort(v, comparer);
    selectionSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
}

TEST(SelectionSortTest, TestThreeElementsSorted) {
    std::vector<std::size_t> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::SelectionSort<std::vector<std::size_t> > selectionSort(v, comparer);
    selectionSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
    EXPECT_EQ(3, v[2]);
}

TEST(SelectionSortTest, TestThreeElementsUnsorted) {
    std::vector<std::size_t> v;
    v.push_back(2);
    v.push_back(1);
    v.push_back(3);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::SelectionSort<std::vector<std::size_t> > selectionSort(v, comparer);
    selectionSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
    EXPECT_EQ(3, v[2]);
}

TEST(SelectionSortTest, TestFullyUnsorted) {
    std::vector<std::size_t> v;
    v.push_back(4);
    v.push_back(3);
    v.push_back(2);
    v.push_back(1);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::SelectionSort<std::vector<std::size_t> > selectionSort(v, comparer);
    selectionSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
    EXPECT_EQ(3, v[2]);
    EXPECT_EQ(4, v[3]);
}

TEST(SelectionSortTest, TestBlockSorted) {
    std::vector<std::size_t> v;
    v.push_back(5);
    v.push_back(6);
    v.push_back(3);
    v.push_back(4);
    v.push_back(1);
    v.push_back(2);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::SelectionSort<std::vector<std::size_t> > selectionSort(v, comparer);
    selectionSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
    EXPECT_EQ(3, v[2]);
    EXPECT_EQ(4, v[3]);
    EXPECT_EQ(5, v[4]);
    EXPECT_EQ(6, v[5]);
}

TEST(SelectionSortTest, TestRepetitionsUnsorted) {
    std::vector<std::size_t> v;
    v.push_back(1);
    v.push_back(3);
    v.push_back(2);
    v.push_back(1);
    v.push_back(2);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::SelectionSort<std::vector<std::size_t> > selectionSort(v, comparer);
    selectionSort.sort();
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(1, v[1]);
    EXPECT_EQ(2, v[2]);
    EXPECT_EQ(2, v[3]);
    EXPECT_EQ(3, v[4]);
}

TEST(SelectionSortTest, TestPerformance) {
    std::vector<std::size_t> v;
    for (int i = 18999; i >= 0; --i)
        v.push_back(i);
    for (int i = 0; i < 1000; ++i)
        v.push_back(i);
    for (int i = 0; i < 1000; ++i)
        v.push_back(10000);
    alg::InPlaceComparer<std::vector<std::size_t> > comparer(v);
    alg::SelectionSort<std::vector<std::size_t> > selectionSort(v, comparer);
    selectionSort.sort();
    EXPECT_EQ(0, v[0]);
    EXPECT_EQ(0, v[1]);
    EXPECT_EQ(1, v[2]);
    EXPECT_EQ(1, v[3]);
    EXPECT_EQ(2, v[4]);
    EXPECT_EQ(2, v[5]);
    EXPECT_EQ(500, v[1000]);
    EXPECT_EQ(1000, v[2000]);
    EXPECT_EQ(1001, v[2001]);
    EXPECT_EQ(1002, v[2002]);
    EXPECT_EQ(8999, v[9999]);
    EXPECT_EQ(10000, v[11000]);
    EXPECT_EQ(10000, v[12000]);
    EXPECT_EQ(10001, v[12001]);
    EXPECT_EQ(18999, v[20999]);
}
